#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0032.py
@time: 2021/11/10 14:27
@desc: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
'''
class Solution:
    def getLeastNumbers(self, arr: list, k: int) -> list:
        def quick_sort(arr, low, high):
            if low<high:
                pivot_pos = partion(arr, low, high)
                quick_sort(arr, low, pivot_pos)
                quick_sort(arr, pivot_pos+1, high)
        def partion(arr, low, high):
            pivot = arr[low]
            while low<high:
                while low<high and arr[high]>=pivot: high -= 1
                arr[low] = arr[high]
                while low<high and arr[low]<=pivot: low += 1
                arr[high] = arr[low]
            arr[low] = pivot
            return low

        def sort(arr):
            # 快排
            quick_sort(arr, 0, len(arr)-1)

        sort(arr)
        return arr[:k]

if __name__ == '__main__':
    arr = [0,1,2,1]
    k = 2
    res = Solution().getLeastNumbers(arr, k)
    print(res)